#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <climits>
#include <cstdlib>

using namespace std;

class Solution {
public:
    int nextGreaterElement(int n) {
        // 将整数转为字符串方便处理
        string numStr = to_string(n);
        int len = numStr.size();
        
        // 从右往左找第一个小于右边某个数字的位置（可以用单调栈优化）
        // 直接方法：找第一个递减的位置
        int i = len - 2;
        while (i >= 0 && numStr[i] >= numStr[i + 1]) {
            i--;
        }
        
        // 如果没有找到，说明已经是最大排列
        if (i < 0) {
            return -1;
        }
        
        // 从i+1到末尾找最小的比numStr[i]大的数字
        int j = len - 1;
        while (j > i && numStr[j] <= numStr[i]) {
            j--;
        }
        
        // 交换i和j位置的字符
        swap(numStr[i], numStr[j]);
        
        // 反转i+1到末尾的所有字符（使其升序）
        reverse(numStr.begin() + i + 1, numStr.end());
        
        // 转换为long long检查是否溢出
        long long result = stoll(numStr);
        
        // 检查是否超出32位整数范围
        if (result > INT_MAX) {
            return -1;
        }
        
        return (int)result;
    }
};

void test01() {
    Solution obj;
    int re = obj.nextGreaterElement(12345);
    cout << "next Greater num:" << re << endl;
}

int main() {
    std::cout << "this is Leetcode-556-demo." << std::endl;

    cout << "test01:" << endl;
    test01();
    return 0;
}
